<!DOCTYPE HTML>
<html lang="zh-CN">




<head>
    <meta charset="utf-8">
    <meta name="keywords" content="Algorithm, 深度学习 故障诊断 Java">
    <meta name="description" content="河海大学 | 计算机与信息学院 | 信号与信息处理">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>Algorithm | 世庆的博客</title>
    <link rel="icon" type="image/png" href="/shiqing/favicon.png">

    <link rel="stylesheet" type="text/css" href="/shiqing/libs/awesome/css/all.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/shiqing/css/my.css">

    <script src="/shiqing/libs/jquery/jquery.min.js"></script>

    <script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>
<meta name="generator" content="Hexo 6.3.0"></head>




    <body>
        <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/shiqing/" class="waves-effect waves-light">
                    
                    <img src="/shiqing/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">世庆的博客</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/tags" class="waves-effect waves-light">
      
      <i class="fas fa-tags" style="zoom: 0.6;"></i>
      
      <span>标签</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/categories" class="waves-effect waves-light">
      
      <i class="fas fa-bookmark" style="zoom: 0.6;"></i>
      
      <span>分类</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/archives" class="waves-effect waves-light">
      
      <i class="fas fa-archive" style="zoom: 0.6;"></i>
      
      <span>归档</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/contact" class="waves-effect waves-light">
      
      <i class="fas fa-comments" style="zoom: 0.6;"></i>
      
      <span>留言板</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/shiqing/friends" class="waves-effect waves-light">
      
      <i class="fas fa-address-book" style="zoom: 0.6;"></i>
      
      <span>友情链接</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>


<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/shiqing/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">世庆的博客</div>
        <div class="logo-desc">
            
            河海大学 | 计算机与信息学院 | 信号与信息处理
            
        </div>
    </div>

    

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/tags" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-tags"></i>
			
			标签
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/categories" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-bookmark"></i>
			
			分类
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/archives" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-archive"></i>
			
			归档
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/contact" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-comments"></i>
			
			留言板
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/shiqing/friends" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-address-book"></i>
			
			友情链接
		</a>
          
        </li>
        
        
        <li><div class="divider"></div></li>
        <li>
            <a href="https://github.com/sqtian-hhu/" class="waves-effect waves-light" target="_blank">
                <i class="fab fa-github-square fa-fw"></i>Fork Me
            </a>
        </li>
        
    </ul>
</div>


        </div>

        
            <style>
    .nav-transparent .github-corner {
        display: none !important;
    }

    .github-corner {
        position: absolute;
        z-index: 10;
        top: 0;
        right: 0;
        border: 0;
        transform: scale(1.1);
    }

    .github-corner svg {
        color: #0f9d58;
        fill: #fff;
        height: 64px;
        width: 64px;
    }

    .github-corner:hover .octo-arm {
        animation: a 0.56s ease-in-out;
    }

    .github-corner .octo-arm {
        animation: none;
    }

    @keyframes a {
        0%,
        to {
            transform: rotate(0);
        }
        20%,
        60% {
            transform: rotate(-25deg);
        }
        40%,
        80% {
            transform: rotate(10deg);
        }
    }
</style>

<a href="https://github.com/sqtian-hhu/" class="github-corner tooltipped hide-on-med-and-down" target="_blank"
   data-tooltip="Fork Me" data-position="left" data-delay="50">
    <svg viewBox="0 0 250 250" aria-hidden="true">
        <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path>
        <path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2"
              fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path>
        <path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z"
              fill="currentColor" class="octo-body"></path>
    </svg>
</a>
        
    </nav>

</header>

        



<div class="bg-cover pd-header post-cover" style="background-image: url('/shiqing/medias/featureimages/9.jpg')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">Algorithm</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/shiqing/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/shiqing/tags/%E7%AE%97%E6%B3%95/">
                                <span class="chip bg-color">算法</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/shiqing/categories/%E7%AE%97%E6%B3%95/" class="post-category">
                                算法
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2021-04-27
                </div>
                

                

                

                

                
            </div>
        </div>
        <hr class="clearfix">

        
        <!-- 是否加载使用自带的 prismjs. -->
        <link rel="stylesheet" href="/shiqing/libs/prism/prism.css">
        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <h3 id="五大常用算法"><a href="#五大常用算法" class="headerlink" title="五大常用算法"></a>五大常用算法</h3><h2 id="一、分治"><a href="#一、分治" class="headerlink" title="一、分治"></a>一、分治</h2><p>分治策略：<br>    1、将原始问题划分或归结为规模较小的子问题。</p>
<pre><code>2、递归或者迭代求解每个子问题

3、将子问题的解综合得到原问题的解

注意：
1、子问题与原问题的性质完全一样

2、子问题之间可以彼此独立求解

3、递归停止时，子问题可以直接求解。

经典问题：Hanoi塔，归并排序，二分检索，芯片测试
</code></pre>
<p>#案例1. Hanoi塔<br>设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，<br>由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的圆盘移到塔座c上，<br>并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：<br>规则1：每次只能移动1个圆盘；<br>规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；<br>规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。<br>思路<br>如果只有 1 个圆盘，a –&gt; c<br>如果圆盘数大于1<br>将 n - 1 个圆盘，从 a 借助 c 移动到 b<br>将剩下 1 个圆盘从 a 移动到 c<br>将 n - 1 个圆盘，从 b 借助 a 移动到 c</p>
<pre><code>@param n 要移动多少个圆盘
@param a 出发地点
@param b 借助地点
@param c 目标地点
public static void move(int n,char a,char b,char c)&#123;
    if (n&lt;1)&#123;
        System.out.println(&quot;请输入正整数&quot;);
    &#125; else if (n == 1) &#123;
        System.out.println(a+&quot;--&gt;&quot;+c);
    &#125;else &#123;
        //先将n-1个盘从a借助c移动到b
        move(n-1,a,c,b);
        //此时,b有n-1个盘,a还剩一个盘,将此盘直接移到c
        move(1,a,b,c);

        //下一个子问题,如何将b的所有盘借助a移动到c
        move(n-1,b,a,c);
    &#125;
&#125;
</code></pre>
<p>#案例2. 芯片测试<br>有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。<br>　　每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。<br>    而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。<br>　　给出所有芯片的测试结果，问哪些芯片是好芯片。</p>
<p>输入格式<br>　　输入数据第一行为一个整数n，表示芯片个数。<br>　　第二行到第n+1行为n*n的一张表，每行n个数据。<br>    表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，<br>    1表示好，0表示坏，i&#x3D;j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。</p>
<p>输出格式<br>　　按从小到大的顺序输出所有好芯片的编号</p>
<p>样例输入<br>3<br>1 0 1<br>0 1 0<br>1 0 1</p>
<p>样例输出<br>1 3</p>
<pre><code>public static ArrayList&lt;Integer&gt; crip(int n, int[][] matrix)&#123;
    /*
     * 要点
     * 本题要点：题目中说：已知好芯片比坏芯片多。
     * 统计矩阵的每一列1的个数，也就是每个芯片被测试为好的次数（包括自己）
     * 如果某芯片被测试为好的次数小于被测试为坏的次数，
     * 如果该芯片为好的，则表示将它测试为坏的那些芯片其实都是坏的
     * 这样坏芯片就比好芯片多，不符合题意
     *
     * 因此,如果被测试为坏的次数多于好,那此芯片指定是坏的
     * 反之,如果测试为好的次数大于坏,那他指定不能是坏的.
     */
    ArrayList&lt;Integer&gt; res = new ArrayList&lt;&gt;();

    //测试为好的次数
    //j列表示芯片对第j个的测试,从j列开始循环读第i个芯片对j的测试
    for (int j = 0;j&lt;n;j++)&#123;
        int tmp = 0;
        for (int i = 0;i&lt;n;i++)&#123;
            if (matrix[i][j] == 1)&#123;
                tmp++;
            &#125;
        &#125;
        if (tmp&gt;n-tmp)&#123;
            res.add(j+1);
        &#125;
    &#125;

    return res;
&#125;
</code></pre>
<h2 id="二、动态规划"><a href="#二、动态规划" class="headerlink" title="二、动态规划"></a>二、动态规划</h2><p>用于解决具有重复子问题和最优子结构的最优化问题。<br>基本思想也是将待求解的问题分解成若干子问题，先求解子问题然后从这些子问题的解得到原问题的解<br>与分治法不同的是，动态规划分解得到的子问题往往不是相互独立的，<br>即上一个子问题的解可能为下一个子问题的条件(通常将结果填入表格)</p>
<p>经典问题：投资问题、背包问题、最长公共子序列</p>
<p>#案例1. 投资问题<br>问题：有m元钱，n项投资，fi(x)：将x元投入第i个项目的效益。求使得的总效益最大的投资方案。<br>建模：问题的解是向量&lt;x1,x2,…,xn&gt;<br>    xi是投给项目i的钱数,i&#x3D;1,2,3,….,n<br>    目标函数F&#x3D;max{f1(x1)+f2(x2)+…+fn(xn)}<br>    约束条件 x1+x2+…+xn&#x3D;m,xi∈N</p>
<p>子问题界定:由参数k和x界定<br>k: 考虑对项目1,2,…,k的投资<br>x: 投资总钱数不超过x</p>
<p>原始输入: k&#x3D;n,x&#x3D;m<br>子问题计算顺序:<br>    k&#x3D;1,2,…,n<br>    对于给定的k,x&#x3D;1,2,…m</p>
<p>递推方程和边界条件<br>    Fk(x) &#x3D; max{fk(xk)+Fk-1(x-xk)}<br>    F1(x) &#x3D; f1(x)</p>
<pre><code>@param m m-1元钱
@param n n个项目
@param tempF 存放投资效益最大值 tempF[i][j]表示j个项目一共投资i元的最高效益
@param d 存放标记解, d[i][j] 表示j个项目一共投i元时,第j个项目投多少元
@param business 效益表 business[i][j] 表示第j个项目投i元的收益
@return 最大利润

public static int investBusiness(int m,int n,int[][] tempF,int[][] d,int[][] business)&#123;
    int sum = 0;

    //先考虑1个项目的情况（1个项目在0到m-1费用之间的效益）
    for (int i = 0;i&lt;m;i++)&#123;
        //只有一个项目时,最高效益表就等于输入效益表的第一列
        tempF[i][0] = business[i][0];
        //第一个项目投资i元
        d[i][0] = i;
    &#125;

    //考虑多个(&gt;=2)项目的情况（多个项目在0到m-1费用之间的效益）
    for (int j = 1;j&lt;n;j++)&#123; //从第二个项目开始
        for (int i = 0;i&lt;m;i++)&#123;
            //最后一个项目投0-i元钱求出最优解
            for (int k = 0;k&lt;i;k++)&#123;
                //Fk(x)=max&#123;fk(xk)+Fk-1(x-xk)&#125;
                sum = business[k][j]+tempF[i-k][j-1];
                if (sum&gt;tempF[i][j])&#123;
                    tempF[i][j] = sum;
                    //j+1个项目一共i元的情况下,记下第j+1个项目应投资k元
                    d[i][j] = k;

                &#125;
            &#125;
        &#125;
    &#125;
    return tempF[m-1][n-1];
&#125;

//解的追踪
public static int[] tracingSolution(int m,int n,int[][] d)&#123;
    //将解寄存在数组里
    int tracing[] = new int[n];
    int s = m-1;

    //最后一个项目应该投资的钱数
    tracing[n-1] = d[m-1][n-1];

    for (int j = n-2;j&gt;=0;j--)&#123;
        //后一个项目的钱投完后剩余的钱
        s -= tracing[j+1];
        //追踪前0-j个项目投s元的分配
        tracing[j] = d[s][j];
    &#125;

    return tracing;
&#125;
</code></pre>
<p>#案例2. 背包问题<br>一个旅行者随身携带一个背包,可以放入背包的物品有n种,每种物品的重量和价值分别为wi,vi<br>如果背包的最大重量限制是b,每种物品可以放多个.<br>怎样选择使背包物品价值最大?<br>建模:<br>解是&lt;x1,x2,…xn&gt;, 其中xi是装入背包的第i种物品个数<br>目标函数: maxΣvixi<br>约束条件: Σwixi&lt;&#x3D;b</p>
<p>子问题界定: 由参数k和y界定 dp[k][y]<br>k: 考虑对物品1,2,…,k的选择<br>y: 背包总重量不超过y</p>
<p>原始输入: k&#x3D;n,y&#x3D;b<br>子问题计算顺序: k &#x3D; 1,2,…,n<br>                对于给定的k,y&#x3D;1,2,…,b</p>
<p>Fk(y): 装前k种物品,总重不超过y,背包达到的最大价值  dp[k][y]<br>Fk(y) &#x3D; max{Fk-1(y),Fk(y-wk)+vk}   dp[k][y] &#x3D; max(dp[k-1][y],dp[k][y-wk])<br>(Fk(y-wk)递归,式子含义是不装第k种的最大价值和第k种至少装一件的最大价值比<br>初值: F0(y) &#x3D; 0, 0&lt;&#x3D;y&lt;&#x3D;b, Fk(0) &#x3D; 0,0&lt;&#x3D;k&lt;&#x3D;n<br>F1(y)&#x3D;[y&#x2F;w1]*v1,Fk(y) &#x3D; -∞ y&lt;0</p>
<p>*第二种写法:<br>与投资问题类似,但时间复杂度比第一种高<br>Fk(y) &#x3D; max{Fk-1(y-xkwk)+xkvk}, 0&lt;&#x3D;xk&lt;&#x3D;[y&#x2F;wk]</p>
<p>*背包问题的推广:</p>
<ol>
<li><p>物品数受限的背包,0-1背包</p>
</li>
<li><p>多背包问题: m个背包,背包j装入最大重量为Bj,j &#x3D; 1,2,…,m</p>
</li>
<li><p>二维背包问题: 每件物品有重量wi和体积ti,背包总重量不超过b,体积不超过V</p>
<p>  static class Materia{<br> public int weight;<br> public int value;<br> public Materia(int weight, int value) {<br>     this.weight &#x3D; weight;<br>     this.value &#x3D; value;<br> }<br> }</p>
<p> @param materia 材料数组<br> @param maxWeight 背包最大承重<br> @param tempF 存放装包价值最大值 tempF[i][j]表示i种材料一共限制j重的最高价值<br> @param d 追踪结果表<br> @return<br> public static int maxLoadingValue(Materia[] materia,int maxWeight,int[][] tempF,int[][] d){<br> int sum &#x3D; 0,tempValue,num&#x3D;d[0][0];<br><br> if (materia.length &#x3D;&#x3D; 0 || maxWeight &#x3D;&#x3D; 0){<br>     return tempF[materia.length-1][maxWeight];<br> }<br><br> &#x2F;&#x2F;初始化<br> &#x2F;&#x2F;只装第一个物品的装包情况,包的容量至少是1,<br> &#x2F;&#x2F;j 1<del>maxWeight<br> for (int j&#x3D;1;j&lt;&#x3D;maxWeight;j++){<br>     tempValue &#x3D; (j&#x2F;materia[0].weight)*materia[0].value;<br>     if (tempValue&gt;sum){<br>         num &#x3D; 1;<br>         sum &#x3D; tempValue;<br>     }<br>     &#x2F;&#x2F;最大价值表记下只有第一种材料的情况下,不同载重的最大价值<br>     tempF[0][j] &#x3D; sum;<br>     &#x2F;&#x2F;追踪表记下载重j只有第一种材料时,上一个放入的都是第一个材料<br>     d[0][j] &#x3D; num;<br> }<br><br><br> &#x2F;&#x2F;装2号之后的材料<br> &#x2F;&#x2F;从i&#x3D;1开始<br> for(int i&#x3D;1;i&lt;materia.length;i++){<br>     &#x2F;&#x2F;装1</del>maxWeight重量<br>     for (int j &#x3D;1;j&lt;&#x3D;maxWeight;j++){<br>         &#x2F;&#x2F;先把num赋为d[i-1][j], 表示目前先拿的材料和只有0~i-1种时相同<br>         num&#x3D;d[i-1][j];<br>         &#x2F;&#x2F;如果放不下新增的第i+1个材料,临时价值量&#x3D;0<br>         &#x2F;&#x2F;临时价值量存的是至少装一个新材料的总价值<br>         if (j-materia[i].weight&lt;0){<br>             tempValue &#x3D; 0;<br>         }else {<br>             &#x2F;&#x2F;Fk(y):装前k种物品,总重不超过y,背包达到的最大价值<br>             &#x2F;&#x2F;Fk(y)&#x3D;max{Fk-1(y),Fk(y-wk)+vk}<br>             &#x2F;&#x2F;装得下第i+1种材料,则要比较至少装一个和不装的价值<br>             &#x2F;&#x2F;Fk(y-wk)+vk<br>             tempValue&#x3D;tempF[i][j-materia[i].weight]+materia[i].value;<br>         }<br>         &#x2F;&#x2F;和不装第i种材料的总价值比较<br>         if (tempValue&gt;&#x3D;tempF[i-1][j]){<br>             if (j-materia[i].weight&gt;&#x3D;0){<br>                 &#x2F;&#x2F;最新一步装第i+1种材料<br>                 num &#x3D; i+1;</p>
</li>
</ol>
<p>&#x2F;&#x2F;                        num++;<br>                    }<br>                    &#x2F;&#x2F;如果装第i+1种材料比不装的价值高,将tempF[i][j]赋成tempValue<br>                    tempF[i][j] &#x3D; tem<br>                    pValue;<br>                } else{<br>                    &#x2F;&#x2F;否则,最大价值依然是只用0~i-1种材料的最优解<br>                  tempF[i][j] &#x3D; tempF[i-1][j];<br>                }<br>                &#x2F;&#x2F;记录i+1种材料,背包载重j的情况下,最先放入的材料是第num号材料<br>                d[i][j] &#x3D; num;<br>            }<br>        }<br>        &#x2F;&#x2F;返回最大价值<br>        return tempF[materia.length-1][maxWeight];<br>    }</p>
<pre><code>public static int[] tracingSolution(int maxWeight,int[][] d,Materia[] materia)&#123;
    //将解寄存在数组里
    //一个k种材料,解的长度为k
    int k = materia.length,count=0,y=maxWeight;
    int[] tracing = new int[k];

    int index = k-1;
    while (y&gt;0&amp;&amp;k&gt;0)&#123;
        //拿到解数组中的最后一个值,表示从最后一种材料开始,先取哪一种材料

        k=d[k-1][y];
        //若是能取到该物品，则对应数组下标中的值+1,表示放该材料的数目+1
        tracing[k-1] = ++count;
        y=y-materia[k-1].weight;

        //如果要取的依然是第k种材料,先把k种材料的解遍历再找d[k-1][y]的解
        while(y&gt;0&amp;&amp;d[k-1][y]==k) &#123;
            tracing[k-1]=++count;
            y=y-materia[k-1].weight;
        &#125;
        count=0;
    &#125;
    return tracing;
&#125;


设序列X,Z
X = &lt;x1,x2,...,xm&gt;
Z = &lt;z1,z2,...,zm&gt;
若存在X的元素构成的严格递增序列使得
zj = xij,j=1,2,...,k
则称Z是X的子序列
即: Z中的元素都是从X中选出来的,且前后次序一样,可以间隔着选

问题: 最长公共子序列
实例: X: A B C B D A B
    Y: B D C A B A
    最长公共子序列: B C B A, 长度4

递推方程:
    Xi = &lt;x1,x2,...,xi&gt;, Yj=&lt;y1,y2,...,yj&gt;
    C[i,j]: Xi与Yj的LCS的长度

C[i,j]= 0, 若 i=0 或 j=0
    = C[i-1,j-1]+1, 若i,j&gt;0,xi = yj
    = max&#123;C[i,j-1],C[i-1,j]&#125;, 若i,j&gt;0,xi != yj
</code></pre>
<p>public class 最长公共子序列 {<br>    public static void main(String[] args) {<br>        &#x2F;&#x2F;随机生成指定长度的字符串<br>        int size &#x3D; 20;<br>        String x  &#x3D; generateRandomStr(size);<br>        String y  &#x3D; generateRandomStr(size);</p>
<pre><code>    int m = x.length();
    int n = y.length();
    //创建二维数组，也就是填表的过程
    int[][] c = new int[m+1][n+1];

    //初始化二维数组
    for (int i = 0; i &lt; m+1; i++) &#123;
        c[i][0] = 0;
    &#125;
    for (int i = 0; i &lt; n+1; i++) &#123;
        c[0][i] = 0;
    &#125;

    //实现公式逻辑
    int[][] path = new int[m+1][n+1];//记录通过哪个子问题解决的，也就是递推的路径
    for (int i = 1; i &lt; m+1; i++) &#123;
        for (int j = 1; j &lt; n+1; j++) &#123;
            if(x.charAt(i-1) == y.charAt(j-1))&#123;
                c[i][j] = c[i-1][j-1] + 1;
            &#125;else if(c[i-1][j] &gt;= c[i][j-1])&#123;
                c[i][j] = c[i-1][j];
                path[i][j] = 1;
            &#125;else&#123;
                c[i][j] = c[i][j-1];
                path[i][j] = -1;
            &#125;
        &#125;
    &#125;
    //输出查看c
    System.out.println(&quot;c:&quot;);
    for (int i = 0; i &lt; m+1; i++) &#123;
        for (int j = 0; j &lt; n+1; j++) &#123;
            System.out.print(c[i][j]+&quot;\t&quot;);
        &#125;
        System.out.println();
    &#125;
    //输出查看path
    System.out.println(&quot;path:&quot;);
    for (int i = 0; i &lt; m+1; i++) &#123;
        for (int j = 0; j &lt; n+1; j++) &#123;
            System.out.print(path[i][j]+&quot;\t&quot;);
        &#125;
        System.out.println();
    &#125;

    System.out.printf(&quot;%s与%s的最长公共子序列为：\n&quot;,x,y);
    PrintLCS(path,x,m,n);


&#125;

public static String generateRandomStr(int length) &#123;
    String base = &quot;ABCDEFGHIJKLMNOPQRSTUVWXYZ&quot;;
    Random random = new Random();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i &lt; length; i++) &#123;
        int number = random.nextInt(base.length());
        sb.append(base.charAt(number));
    &#125;
    return sb.toString();
&#125;


public static void PrintLCS(int[][]b,String x,int i,int j)&#123;
    if(i == 0 || j == 0)&#123;
        return;
    &#125;

    if(b[i][j] == 0)&#123;
        PrintLCS(b,x,i-1,j-1);
        System.out.printf(&quot;%c&quot;,x.charAt(i-1));
    &#125;else if(b[i][j] == 1)&#123;
        PrintLCS(b,x,i-1,j);
    &#125;else&#123;
        PrintLCS(b,x,i,j-1);
    &#125;
&#125;
</code></pre>
<h2 id="三、贪心"><a href="#三、贪心" class="headerlink" title="三、贪心"></a>三、贪心</h2><p>贪心算法可以获取到问题的局部最优解，不一定能获取到全局最优解<br>同时获取最优解的好坏要看贪心策略的选择<br>特点就是简单，能获取到局部最优解</p>
<p>经典问题：单源最短路径、最小生成树、哈夫曼算法、找零钱问题、最优装载问题、最小延迟调度、活动选择问题</p>
<p>#案例1. 单源最短路径(Dijkstra算法)</p>
<p>给定带权有向网络 G&#x3D;(V,E,W),每条边 e&#x3D;&lt;i,j&gt;的权w(e)为非负实数<br>表示从i到j的距离<br>求从s出发到达其它结点的最短路径</p>
<p>算法思想的简单描述：<br>要找出源到其他顶点的最短距离，首先将所有顶点划分成两个集合，S是已经到达的顶点，V是没有到达的顶点，显然S+V就是所有顶点。<br>初始，S集合中只包含源顶点（本例中是1号顶点），然后找出V中距离S集合最近的一个顶点<br>（即贪心选择，至于为什么是S集合，请务必理解该问题的最优子结构性质）。<br>那么显然，需要有个对象来记录每个顶点到源顶点的距离，这就是代码中的dist数组。<br>dist[2]&#x3D;x就表示，顶点2到源顶点的最短距离是x。找到后，记录下路径。<br>如何记录，同样需要一个对象，即代码中的prev数组。prev[2]&#x3D;y就表示，顶点2到源顶点的最短路径中，顶点2的前一个顶点是顶点y。<br>记录下路径的同时还需要将该顶点加入到S集合中,它就是s数组了。</p>
<p>初始: S&#x3D;{s},S&#x3D;V时算法结束<br>从s到u相对于S的最短路径: 从s到u且仅经过S中顶点的最短路径<br>dist[u]: 从s到u相对于S最短路径的长度<br>short[u]: 从s到u的最短路径的长度<br>dist[u]&gt;&#x3D;short[u]</p>
<p>
输入:有向图
输出:从s到每个顶点的最短路径

<pre><code>static float max = Float.MAX_VALUE;
@param v    源
@param a    图
@param dist 路径长度
@param prev 路径

public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) &#123;
    // v是源，dist[i]表示当前从源到顶点i的最短特殊路径长度,prev[i]=j：最短路径中顶点i的前一个顶点是j，类似于链表
    int n = dist.length - 1;// 节点个数
    //如果出发源不在节点范围
    if (v &lt; 0 || v &gt; n) &#123;
        return;
    &#125;

    //S集合标记ture的在S中，false的不在
    boolean[] s = new boolean[n + 1];

    // 初始化
    for (int i = 0; i &lt;= n; i++) &#123;
        //a[v][i] 从v到i的路径，没有边则是max
        dist[i] = a[v][i];
        //初始时节点不在集合S中
        s[i] = false;
        if (dist[i] == Float.MAX_VALUE)
            //没有边相连时路径链表初始化为0
            prev[i] = 0;
        else
            //有边直接相连的路径链表初始化为v
            prev[i] = v;
    &#125;

    dist[v] = 0;
    //v点初始在S集合中
    s[v] = true;

    // 循环n+1次,直到所有点加进了S集合
    for (int i = 0; i &lt;= n; i++) &#123;
        float temp = Float.MAX_VALUE;
        int u = v;

        //第一次循环找出距离集合最近的节点u
        for (int j = 0; j &lt;= n; j++) &#123;
            // 寻找不在集合内且距离集合最近的节点j
            if ((!s[j]) &amp;&amp; (dist[j] &lt; temp)) &#123;
                u = j;// 记录节点
                temp = dist[j];// 记录最短特殊路径长度
            &#125;
        &#125;

        s[u] = true;// 将节点u放入集合

        //第二次循环找出经由u能够到达的节点
        for (int j = 0; j &lt;= n; j++) &#123;// 重新设置dist[]和prev[]的值
            if ((!s[j]) &amp;&amp; (a[u][j] &lt; max)) &#123;// 寻找不在集合内，且可达的节点

                //新的距离等于从v到u的最短距离+从u到j的距离
                float newdist = dist[u] + a[u][j];
                if (newdist &lt; dist[j]) &#123; // 与旧值进行比较，保留小的值
                    dist[j] = newdist;
                    prev[j] = u;
                &#125;
            &#125;
        &#125;
    &#125;
&#125;
</code></pre>
<p>#案例2. 最小生成树<br>G的一棵生成树T是包含了G的所有顶点的树，树中各边的权之和W(T)称为树的权,具有最小权的生成树称为G的最小生成树</p>
<pre><code>#kruskal算法
</code></pre>
<p> 设计思想:</p>
<ol>
<li>按照长度从小到大对边排序</li>
<li>依次考察当前最短边e,如果e与T的边不构成回路,则把e加入树T,否则跳过e.直到选择了n-1条边为止</li>
</ol>
<p> 算法实现:<br> 建立FIND数组,FIND[i]是结点i的连通分支标记</p>
<ol>
<li>初始FIND[i] &#x3D; i</li>
<li>连通分支合并,较小分支标记更新为较大分支标记</li>
</ol>
<p> 应用:数据分组问题<br> 一组数据要把它们按照相关性进行分类 单链聚类</p>
<p> 具体步骤<br> 1.将图的所有连接线去掉，只剩顶点</p>
<p> 2.从图的边集数组中找到权值最小的边，将边的两个顶点连接起来</p>
<p> 3.继续寻找权值最小的边，将两个顶点之间连接起来，如果选择的边使得最小生成树出现了环路，则放弃该边，选择权值次小的边</p>
<p> 4.直到所有的顶点都被连接在一起并且没有环路，最小生成树就生成了。</p>
<p> 使用并查集思路</p>
<p>public class 最小生成树Kruskal算法 {<br>    public static void main(String[] args) {<br>        int[][] edges &#x3D; {<br>&#x2F;&#x2F;              begin, end, weight<br>                {0, 1, 6},<br>                {0, 2, 1},<br>                {0, 3, 5},<br>                {2, 1, 5},<br>                {2, 3, 5},<br>                {2, 4, 5},<br>                {2, 5, 4},<br>                {1, 4, 3},<br>                {4, 5, 6},<br>                {5, 3, 2}<br>        };</p>
<pre><code>    int n = 6;
    int[][] mstEdges = kruskal(n, edges);

    int totalCost = 0;
    System.out.println(&quot;Edges of MST: [node1, node2, cost]&quot;);
    //输出构树的边集
    for (int i = 0; i &lt; mstEdges.length; i++) &#123;
        int[] edge = mstEdges[i];
        for (int j = 0; j &lt; edge.length; j++) &#123;
            System.out.print(edge[j] + &quot; &quot;);
        &#125;
        totalCost += edge[2];
        System.out.println();
    &#125;

    System.out.println(&quot;Total cost of MST: &quot; + totalCost);
&#125;

public static int[][] kruskal(int n, int[][] edges) &#123;
    /**
     * @Description: 克鲁斯卡尔算法求最小生成树
     * @Param: [n, edges] ==&gt; [结点个数， 边集]
     * @return: int[] 构成最小生成树的边集
     */
    int[] pres = new int[n]; //并查集
    int[] ranks = new int[n]; //结点的秩,树的层数?

    // 初始化：pres一开始设置每个元素的上一级是自己，ranks一开始设置每个元素的秩为0
    for (int i = 0; i &lt; n; i++) &#123;
        pres[i] = i;
        ranks[i] = 0;
    &#125;

    //用自己定义的MyEdge类里面的compareTo排序，按边权排序
    ArrayList&lt;MyEdge&gt; edgesList = new ArrayList&lt;&gt;();
    for (int i = 0; i &lt; edges.length; i++) &#123;
        edgesList.add(new MyEdge(edges[i]));
    &#125;
    // 边集从小到大排序
    Collections.sort(edgesList);

    //最小生成树的边
    int[][] mstEdges = new int[n - 1][3];
    int count = 0;
    for (int i = 0; i &lt; edgesList.size(); i++) &#123;
        int[] arr = edgesList.get(i).array;
        int a = arr[0], b = arr[1], c = arr[2];
        //边的两个节点不在同一个集合里,合并
        if (find(a, pres) != find(b, pres)) &#123;
            unionSet(a, b, pres, ranks);
            //添加到结果集合中
            mstEdges[count] = arr;
            count++;
        &#125;
        //如果两个节点的根节点相同,说明已经划在了结果集合里,这条边会构成闭环,不添加

        //连接好了所有节点, 所有节点都在一个集合了
        if (count == n) &#123;
            break;
        &#125;
    &#125;
    //返回结果
    return mstEdges;
&#125;


//并查集

//并：合并两个集合，按秩合并
public static void unionSet(int n1, int n2, int[] pres, int[] ranks) &#123;
    int root1 = find(n1, pres);
    int root2 = find(n2, pres);
    //当两个元素不是同一组的时候才合并
    //两个节点的连接根节点不同
    if (root1 != root2) &#123;
        //把节点数少的一组划归大的一组
        if (ranks[root1] &lt; ranks[root2]) &#123;
            pres[root1] = root2;
        &#125; else &#123;
            pres[root2] = root1;
            //如果两组个数相等,结点层数+1
            if (ranks[root1] == ranks[root2])
                ranks[root1]++;
        &#125;
    &#125;
&#125;

//查：查找元素的根节点
public static int find(int x, int[] pres) &#123;
    int root = x;
    //如果此结点上级结点不是自己,继续向上搜索
    while (pres[root] != root)
        root = pres[root];

    //循环后,找到根节点为root

    //路径压缩
    int p = x;
    while (pres[p] != p) &#123;
        //把所有结点的上级节点都设置成root
        int t = pres[p];
        pres[p] = root;
        p = t;
    &#125;
    return root;
&#125;
</code></pre>
<p>}</p>
<p>&#x2F;&#x2F; 边的排序类<br>class MyEdge implements Comparable {<br>    int[] array;</p>
<pre><code>MyEdge(int[] array) &#123;
    this.array = array;
&#125;

@Override
public int compareTo(Object o) &#123;
    o = (MyEdge) o;
    int[] arr = ((MyEdge) o).array;
    if (array[2] &gt; arr[2]) &#123;
        return 1;
    &#125; else if (array[2] == arr[2]) &#123;
        return 0;
    &#125; else &#123;
        return -1;
    &#125;
&#125;
</code></pre>
<p>}</p>
<pre><code>#prim算法
</code></pre>
<p>prim设计思想<br>输入: 图G&#x3D;(V,E,W),V 节点,E 边,W 权值, V&#x3D;{1,2,…,n}<br>输出: 最小生成树T<br>初始S &#x3D; {1}<br>选择连接S与V-S集合的最短边e&#x3D;{i,j},其中i∈S,j∈V-S.将e加入树T,j加入S<br>继续执行上述过程,直到S&#x3D;V</p>
<p>prim以点出发, kruskal以边出发</p>
<p>public class 最小生成树Prim算法 {<br>    public static void main(String[] args) {<br>&#x2F;&#x2F;交互输入图的邻接矩阵表示，为方便测试，直接给定了邻接矩阵值<br>&#x2F;&#x2F;		System.out.println(“请输入图定点个数： “);<br>&#x2F;&#x2F;		Scanner sc &#x3D; new Scanner(System.in);<br>&#x2F;&#x2F;		String line &#x3D; sc.nextLine();<br>&#x2F;&#x2F;		int n &#x3D; Integer.parseInt(line);<br>&#x2F;&#x2F;		System.out.println(“请输入图的路径长度: “);<br>&#x2F;&#x2F;		int[][] c &#x3D; new int[n+1][n+1];<br>&#x2F;&#x2F;		for(int i &#x3D; 0; i &lt; n; i++) {<br>&#x2F;&#x2F;			line &#x3D; sc.nextLine();<br>&#x2F;&#x2F;			String[] ds &#x3D; line.split(“,”);<br>&#x2F;&#x2F;			for(int j &#x3D; 0;j &lt; ds.length; j++) {<br>&#x2F;&#x2F;				c[i+1][i+1] &#x3D; Integer.parseInt(ds[j]);<br>&#x2F;&#x2F;<br>&#x2F;&#x2F;			}<br>&#x2F;&#x2F;		}<br>&#x2F;&#x2F;		System.out.println(“一次构成树的边为： “);<br>        int n &#x3D; 6;<br>        &#x2F;&#x2F;c[i][j]表示从i到j的权，为了方便对应索引，ｃ[0][j]和c[i][0]都设置成0</p>
<p>&#x2F;&#x2F;        自己到自己的权，以及不能直接到的值置-1，方便后面处理<br>        int[][] c &#x3D; {<br>                {0,0,0,0,0,0},<br>                {0,-1,6,1,5,-1,-1},<br>                {0,6,-1,5,-1,3,-1},<br>                {0,1,5,-1,5,6,4},<br>                {0,5,-1,5,-1,-1,2},<br>                {0,-1,3,6,-1,-1,6},<br>                {0,-1,-1,4,2,6,-1}<br>        };<br>        prim(n,c);</p>
<pre><code>&#125;
public static void prim(int n, int[][] c) &#123;
    //lowcost[i] 表示 从1到i的最短权值
    int[] lowcost = new int[n+1];
    //closest[i]的表示：
</code></pre>
<p>&#x2F;&#x2F;        将整个节点空间定为V，已选的空间从S&#x3D;1（只有第一个点）开始，<br>&#x2F;&#x2F;        j在V-S中，找到S里离j最近的节点i ，就记录在closest[j]。<br>        int[] closest &#x3D; new int[n+1];<br>        &#x2F;&#x2F;哪些节点已经进入S空间<br>        boolean[] s &#x3D; new boolean[n+1];<br>        &#x2F;&#x2F;节点1进入S中，此为初始化<br>        s[1] &#x3D; true;<br>        &#x2F;&#x2F;初始化<br>        for(int i &#x3D; 2; i &lt;&#x3D; n; i++) {<br>            &#x2F;&#x2F;初始化第一个节点到每个节点权值<br>            lowcost[i] &#x3D; c[1][i];<br>            &#x2F;&#x2F;初始化，因为S中只有1，所以每个V-S中的节点最近的S中的节点一定是1<br>            closest[i] &#x3D; 1;<br>            &#x2F;&#x2F;这些节点都初始化为不在S中的状态<br>            s[i] &#x3D; false;<br>        }</p>
<pre><code>    //n-1次遍历，把S空间扩充成V
    for(int i = 1;i &lt; n; i++) &#123;
        //记录一个当前最小权值，不断比较最终变为整个1次遍历过程的最小权值
        int min = Integer.MAX_VALUE;
        //初始化j，j其实代表的是V-S空间中被选进S的节点
        //它的特征是，它到S（任何节点）的权值比其他节点到S（同样随便哪个节点）都小
        //这里的思想就是贪心的概念，通过局部最优可以得到全局最优
        int j = 1;
        //遍历除了直接初始化在S中的1节点外的其他所有节点
        for(int k = 2; k &lt;= n; k++) &#123;
            //不等于-1即，直接有权值，然后迭代出最小的lowcost，同时更新一些值。
            //这里举例更容易说明，如lowcost[k]其实代表的是目前的S空间到k的最小权值，
            // 迭代找到了这个k，那么 显然 j就应该是k
            if(lowcost[k] != -1 &amp;&amp; lowcost[k] &lt; min &amp;&amp; !s[k]) &#123;
                min = lowcost[k];
                j = k;
            &#125;
        &#125;
        //输出这对连接，closest[j]记录的其实就是达成lowcost[k]这一最小权值时，S中具体是哪个节点
        System.out.println(closest[j] + &quot;-&quot; + j);
        //如此，把j纳入S空间
        s[j] = true;
        //j进入S空间后，更新除1节点外所有节点的状态，他们到S的最小权值还得看看他们到 新进入的j是否更小
        for(int k = 2; k &lt;= n; k++) &#123;
            if(!s[k] &amp;&amp; c[j][k] != -1) &#123;
                //这里注意，如果lowcost[k]本来是-1
                //说明本来都不相连直接可以更新了
                //这里的逻辑要搞清楚，先判断有必要更新么？（c[j][k]!= -1),
                // 然后判断 要么c[j][k]比之前的权值更小，
                // 要么原来都不相连（c[j][k] &lt; lowcost[k] || lowcost[k] == -1) 此时进行更新！
                if(c[j][k] &lt; lowcost[k] || lowcost[k] == -1) &#123;
                    //更新该节点最小的权值
                    lowcost[k] = c[j][k];
                    //更新该节点在S中最近的点
                    closest[k] = j;
                &#125;
            &#125;
        &#125;

    &#125;
&#125;
</code></pre>
<p>}</p>
<h2 id="四、回溯"><a href="#四、回溯" class="headerlink" title="四、回溯"></a>四、回溯</h2><p>回溯算法基本思想</p>
<ol>
<li>适用：求解搜索问题和优化问题</li>
<li>搜索空间：树，结点对应部分解向量，可行解在树叶上</li>
<li>搜索过程：采用系统的方法隐含遍历搜索树</li>
<li>搜索策略： 深度优先，宽度优先，函数优先，宽深结合等</li>
<li>结点分支判定条件： 满足约束条件-分支扩张解向量不满足约束条件，回溯到该结点的父结点</li>
<li>结点状态： 动态生成 白结点（尚未访问）  灰结点（正在访问该结点为根的子树） 黑结点（该结点为根的子树遍历完成）</li>
<li>存储： 当前路径</li>
</ol>
<p>经典问题：n后放置、图的着色、装载问题、货郎问题、零一背包</p>
<p>#案例1. 4后问题</p>
<p>在4*4的方格棋盘上放置4各皇后,使得没有两个皇后在同一行、同一列<br>也不在同一条45度斜线上<br>问有多少种可能的布局</p>
<p>解N皇后问题需要遍历解空间树，遍历中要随时判定当前结点棋盘布局是否符合要求，<br>符合要求则继续向下遍历，直至判断得到一个满足约束条件的叶子结点，从而获得一个满足要求的棋盘布局；<br>不符合要求的结点将被舍弃（称之为剪枝），并回溯到上一层的结点继续遍历。<br>当整棵树遍历结束时，已获得所有满足要求的棋盘布局。</p>
<p>public class n后放置 {<br>    static int resultCount &#x3D; 0;<br>    &#x2F;*<br>     * 皇后位置满足约束条件的判定函数<br>     *&#x2F;<br>    private static boolean place(int[] X,int s) {<br>        &#x2F;&#x2F;判定s行X[s]列位置上的皇后，与1至s-1行上各皇后的位置是否满足约束条件<br>        for(int i &#x3D; 0; i &lt; s; i++) {</p>
<pre><code>        if((X[i] == X[s]) || (Math.abs(i-s) == Math.abs(X[i]-X[s]))) &#123; //行差i-s的绝对值 = 列差的绝对值
            return false;
        &#125;
    &#125;

    return true;
&#125;


/*
 * 求解N皇后问题的回溯算法
 * 棋盘为n*n，函数从第index行起求解皇后的布局，本函数初始调用为tria(queen, 0, n)
 * arr[n]为可行解
 */

public static void tria(int[] arr, int i, int n) &#123;
    //递归终止条件
    //放完最后一个了
    if(i &gt;= n) &#123;
        // TODO 输出X数组（也可以改写算法，比如记录满足约束的棋盘个数）
        for(int in= 0;in&lt;arr.length;in++)&#123;
            System.out.print(arr[in]+&quot; &quot;);
        &#125;

        System.out.println();
        ++resultCount;
        return;
    &#125;
    
    //dfs
    for(int j = 0; j &lt; n; j++) &#123;
        //如果第i个皇后放在j位置满足要求,继续tria
        arr[i] = j;
        if(place(arr, i)) &#123;
            tria(arr, i+1, n);
        &#125;
    &#125;

&#125;

public static void main(String[] args) &#123;
    Scanner sc = new Scanner(System.in);
    System.out.println(&quot;一共n个皇后&quot;);
    int num = sc.nextInt();
    int[] queen = new int[num];
    tria(queen, 0, num);

    System.out.println(resultCount);
&#125;
</code></pre>
<p>}</p>
<p>#案例2. 图的着色问题<br>输入：<br>无向连通图G和m种颜色集合用这些颜色给图的顶点着色<br>每个顶点一种颜色。要求是： G的每条边的两个顶点着不同颜色<br>输出：<br>所有可能的着色方案<br>如果不存在着色方案，回答“No”</p>
<p>
着色问题的应用
会场分配问题： 有n项活动需要安排，对于活动i，j，如果i，j时间冲突
就说i与j不相容。如何分配这些活动，使得每个会场相容且占用会场最少


<p>public class 图的着色问题 {</p>
<pre><code>int n;//图的顶点数
int m;//可用颜色数
int[][] a;//图的邻接矩阵
int[] x;//当前解
long sum;//当前已找到的可着色方案数

public long mcoloring(int mm, int nn, int[][] aa) &#123;
    n = nn;
    a = aa;
    x = new int[n + 1];
    m = mm;
    sum = 0;
    tria(1);
    return sum;
&#125;

public void tria(int t) &#123;
    //递归终止条件
    if (t &gt; n) &#123;
        //全部涂完的结果
        sum++;
        for (int i = 1; i &lt;= n; i++)
            System.out.print(x[i] + &quot; &quot;);
        System.out.println();
        return;
    &#125;
    
    for (int i = 1; i &lt;= m; i++) &#123;
        //给第t个点上第i种色
        x[t] = i;
        //涂色合法则继续涂下一个
        if (ok(t))//剪枝函数
            tria(t + 1);
        //不合法则置为0，不合法的都是0,判断x[j] == x[k]时为false剔除
        x[t] = 0;
    &#125;
    
&#125;

//判断涂色是否合法的方法
public boolean ok(int k) &#123;
    for (int j = 1; j &lt;= n; j++) &#123;
        //与k相连的点且两点颜色相同则判false
        if (a[k][j] == 1 &amp;&amp; x[j] == x[k])//某条边的两个顶点着不同颜色；a[k][j]=1表示某条边（即边集E中的边）
            return false;
    &#125;
    return true;
&#125;

public static void main(String[] args) &#123;

    int n = 5;
    int m = 5;
    int[][] a = &#123;
            &#123;-1, -1, -1, -1, -1, -1&#125;,
            &#123;-1, 0, 1, 1, 1, 0&#125;,
            &#123;-1, 1, 0, 1, 1, 1&#125;,
            &#123;-1, 1, 1, 0, 1, 0&#125;,
            &#123;-1, 1, 1, 1, 0, 1&#125;,
            &#123;-1, 0, 1, 0, 1, 0&#125;&#125;;
    图的着色问题 c = new 图的着色问题();
    System.out.println(&quot;着色方案如下：&quot;);
    long sum = c.mcoloring(m, n, a);
    System.out.println(&quot;可行的着色方案数目为：&quot; + sum);
&#125;
</code></pre>
<p>}</p>
<p>#案例3. 装载问题<br>有n个集装箱，需要装上两艘载重分别为c1，c2的轮船<br>wi为第i个集装箱的重量，且w1+w2+…+wn&lt;&#x3D;c1+c2<br>问：是否存在一种合理的装载方案把这n个集装箱装上船？</p>
<p>输入：集装箱重量 向量，c1，c2<br>算法思想： 令第一艘船的装入量为W1</p>
<ol>
<li>用回溯算法求使得c1-W1达到最小的装载方案第一艘船尽可能多装</li>
<li>若满足 w1+w2+…+wn-W1&lt;&#x3D;c2，看剩下的第二艘装不装得下，装得下则回答yes，否则回答no</li>
</ol>
<p>算法</p>
<ol>
<li>从大到小排序</li>
<li>B &lt;- c1; best &lt;- c1;i &lt;- 1         B为当前空隙，best为最小空隙</li>
<li>while i&lt;&#x3D;n do</li>
<li>if 装入i后重量不超过c1</li>
<li>then B&lt;-B-wi;x[i]&lt;-1;i&lt;-i+1</li>
<li>else x[i]&lt;- 0;i&lt;-i+1;</li>
<li>if B&lt;best then 记录解;best &lt;- B;</li>
<li>Backtrack(i);   回溯</li>
<li>if i&#x3D;1 then return 最优解</li>
<li>else goto 3</li>
</ol>
<p>回溯过程：Backtrack(i)<br>while i&gt;1 and x[i] &#x3D; 0 do<br>     i &lt;- 1;<br>if x[i] &#x3D; 1;<br>then x[i] &lt;- 0;<br>     B &lt;- B+wi<br>     i &lt;- i+1</p>
<p>public class 装载问题{</p>
<pre><code>static int c;//船的载重量
static int n;//物品数量
static int[] w;//物品的重量
static int cw;//当前船的载重量
static int bestw;//当前最优载重量（最大载重量）
static int r;//剩余物品重量-----未考察过的物品的重量，并非没有装载的物品的重量，所以考察到就减去

static int[] X;//是否装载当前深度的物品，装载则X[i]=1，不装载则X[i]=0
static int[] Xbest;//记录最优解，最优路径

public static void main(String[] args) &#123;

    int w[] = &#123;0, 20, 30, 60, 40, 40&#125;;
    int c = 100;
    int n = w.length - 1;
    System.out.print(&quot;货物重量为： &quot;);
    for (int i = 1; i &lt;= n; i++) &#123;
        System.out.print(w[i] + &quot;  &quot;);
    &#125;
    System.out.println();
    System.out.println(&quot;第一艘船载重量为： &quot; + c);
    System.out.println(&quot;第二艘船载重量为： &quot; + c);

    Initialize(w, c);
    int weight2 = 0;
    for (int i = 1; i &lt;= n; i++) &#123;
        weight2 += w[i] * (1 - Xbest[i]);
    &#125;
    if (weight2 &gt; c)
        System.out.println(&quot;无解！&quot;);
    else &#123;
        System.out.println(&quot;第一艘船的货物载重为： &quot; + bestw);
        System.out.println(&quot;第二艘船的货物载重为： &quot; + weight2);
        for (int i = 1; i &lt;= n; i++) &#123;
            if (Xbest[i] == 1)
                System.out.println(&quot;第&quot; + i + &quot;件物品装入第一艘船&quot;);
        &#125;
        for (int i = 1; i &lt;= n; i++) &#123;
            if (Xbest[i] == 0)
                System.out.println(&quot;第&quot; + i + &quot;件物品载入第二艘船&quot;);
        &#125;
    &#125;
&#125;

public static int Initialize(int[] weight, int capacity) &#123;

    n = weight.length - 1;
    w = weight;
    c = capacity;
    bestw = 0;
    cw = 0;
    r = 0;
    X = new int[n + 1];
    Xbest = new int[n + 1];
    for (int i = 1; i &lt;= n; i++) &#123;
        r = r + w[i];
    &#125;//记录最大剩余物品重量，也就是总重量
    Backtrack(1);
    return bestw;
&#125;

public static void Backtrack(int i) &#123;
    if (i &gt; n) &#123;//i&gt;n，表示已经到叶子节点
        if (cw &gt; bestw) &#123;
            for (int j = 1; j &lt;= n; j++)
                Xbest[j] = X[j];//记录最优路径
        &#125;
        bestw = cw;//若cw&lt;bestw，更新bestw=cw
        return;
    &#125;
    r = r - w[i];//计算剩余（未考察）的物品的重量，减去当前考察过的对象的重量
    //剪枝函数
    if (cw + w[i] &lt;= c) &#123;//约束函数
        cw = cw + w[i];//进入子树，则+
        X[i] = 1;//左子树1，右子树0
        Backtrack(i + 1);
        cw = cw - w[i];//到这来表示已经从Backtrack(i+1)里出来，则要复原cw，所以前面+，这里则-，恢复原状。
    &#125;
    if (cw + r &gt; bestw) &#123;//限界函数，如果cw+r不大于bestw，则不用进入下一层了，因为进入也不大于bestw
        //这里不用约束函数，因为不取X[i]=0则一定不会大于c
        //因为r值是累计的(在Backtrack(i+1)里)，所以已经减了r=r-w[i]已经减去了w[i]，
        // 当你退出Backtrack(i+1)后，返回上一层回溯，就得恢复r，所以有r=r+w[i]
        X[i] = 0;
        Backtrack(i + 1);
    &#125;
    r = r + w[i];//递归回退返回上一层时，记得修改r的当前值，如果得不到最优解，
    // 再取消当前考察的集装箱，标记为未选，因此剩余容量要再加上当前集装箱重量
&#125;
</code></pre>
<p>}</p>
<p>#案例4. 货郎问题<br>有n个城市,已知任两个城市之间的距离,求一条每个城市恰好经过一次的回路<br>使得总长度最小</p>
<p>
注意哈密顿回路和TSP之间的区别。哈密顿回路问题是要找出是否存在一个旅游线路，每个城市访问一次。
这里我们知道哈密顿回路存在（因为图是完整的），事实上存在许多这样的回路，
问题是找到一个最小权重的哈密顿回路。


<p>public class 货郎问题 {<br>    static int INF &#x3D; (int) 1e7;&#x2F;&#x2F;设置无穷大的值为10的七次方<br>    static int N &#x3D; 100;<br>    static int[][] g &#x3D; new int[N][N];&#x2F;&#x2F;地图的无向带权邻接矩阵<br>    static int[] x &#x3D; new int[N];&#x2F;&#x2F;记录当前路径<br>    static int[] bestx &#x3D; new int[N];&#x2F;&#x2F;记录当前最优路径<br>    static int cl;&#x2F;&#x2F;当前路径长度<br>    static int bestl;&#x2F;&#x2F;当前最短路径长度<br>    static int n, m;&#x2F;&#x2F;城市个数n,边数m</p>
<pre><code>static void swap(int array[], int a, int b) &#123;//交换函数
    int temp;
    temp = array[a];
    array[a] = array[b];
    array[b] = temp;
&#125;

static void Traveling(int t) &#123;
    if (t &gt; n) &#123;//到达叶子节点
        /*
        推销货物的最后一个城市与住地城市有边相连并且路径长度比当前最优值小，说明找到了一条更好的路径，记录相关信息
         */
        if (g[x[n]][1] != INF &amp;&amp; (cl + g[x[n]][1] &lt; bestl)) &#123;
            for (int j = 1; j &lt;= n; j++) &#123;
                bestx[j] = x[j];
            &#125;
            bestl = cl + g[x[n]][1];
        &#125;
    &#125; else &#123;//没有到达叶子节点
        for (int j = t; j &lt;= n; j++) &#123;//搜索扩展节点的所有分支
            if (g[x[t - 1]][x[j]] != INF &amp;&amp; (cl + g[x[t - 1]][x[j]] &lt; bestl)) &#123;
                //如果第t-1个城市与第t个城市有边相连并且有可能得到更短的路线
                swap(x, t, j);//交换两个元素的值
                cl = cl + g[x[t - 1]][x[t]];
                Traveling(t + 1);//从第t+1层的扩展结点继续搜索
                //第t+1层搜索完毕，回溯到第t层原始状态
                cl = cl - g[x[t - 1]][x[t]];
                swap(x, t, j);
            &#125;
        &#125;
    &#125;
&#125;

//初始化函数
static void init() &#123;
    bestl = INF;
    cl = 0;
    for (int i = 1; i &lt;= n; i++)
        for (int j = i; j &lt;= n; j++)
            g[i][j] = g[j][i] = INF;
    for (int i = 0; i &lt;= n; i++) &#123;
        x[i] = i;
        bestx[i] = 0;
    &#125;
&#125;

static void print() &#123;
    System.out.print(&quot;最短路径：&quot;);
    for (int i = 1; i &lt;= n; i++) &#123;
        System.out.print(bestx[i] + &quot;----&gt;&quot;);
    &#125;
    System.out.println(&quot;1&quot;);
    System.out.print(&quot;最短路径长度：&quot; + bestl);
&#125;

public static void main(String[] args) &#123;
    Scanner sc = new Scanner(System.in);
    int u, v, w;//u,v代表城市，w代表城市u,v之间的距离。
    System.out.println(&quot;请输入城市数n：&quot;);
    n = sc.nextInt();
    init();
    System.out.println(&quot;请输入城市之间的连线数：&quot;);
    m = sc.nextInt();
    System.out.println(&quot;请依次输入两个城市u,v以及之间的距离w:&quot;);
    for (int i = 1; i &lt;= m; i++) &#123;
        u = sc.nextInt();
        v = sc.nextInt();
        w = sc.nextInt();
        g[u][v] = g[v][u] = w;
    &#125;
    Traveling(2);//根据排列树的图，从第二层开始
    print();
&#125;
</code></pre>
<p>}</p>
<p>&#x2F;&#x2F;<br>&#x2F;&#x2F;                { 0, 10, 15, 20 },<br>&#x2F;&#x2F;                        { 10, 0, 35, 25 },<br>&#x2F;&#x2F;                        { 15, 35, 0, 30 },<br>&#x2F;&#x2F;                        { 20, 25, 30, 0 }</p>
<p>&#x2F;&#x2F;请输入城市数n：<br>&#x2F;&#x2F;        ４<br>&#x2F;&#x2F;        请输入城市之间的连线数：<br>&#x2F;&#x2F;        １２<br>&#x2F;&#x2F;        请依次输入两个城市u,v以及之间的距离w:<br>&#x2F;&#x2F;        １　２　１０<br>&#x2F;&#x2F;        １　３　１５<br>&#x2F;&#x2F;        １　４　２０<br>&#x2F;&#x2F;        ２　１　１０<br>&#x2F;&#x2F;        ２　３　３５<br>&#x2F;&#x2F;        ２　４　２５<br>&#x2F;&#x2F;        ３　１　１５<br>&#x2F;&#x2F;        ３　２　３５　３　４　３０　４　１　２０　４　２　２５　４　３　３０<br>&#x2F;&#x2F;        最短路径：1—-&gt;2—-&gt;4—-&gt;3—-&gt;1<br>&#x2F;&#x2F;        最短路径长度：80<br>&#x2F;&#x2F;        Process finished with exit code 0</p>
<p>#案例5. 零一背包<br>回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，<br>这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。<br>许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。</p>
<p>有n种物品，每种物品只有一个，第i种物品价值为vi，重量为wi，i&#x3D;1，2，3…n<br>问如何选择放入背包的物品,使得总重量不超过B而价值达到最大</p>
<p>用回溯法实现0-1背包问题。<br>在回溯开始之前，首先对于背包中的物品按照单位重量价值进行排序，方便于后面右子树的剪枝操作。<br>在初始化物品的重量和价值时，已经按照单位重量的价值排好了序。<br>一个典型的子集树问题，对于背包中的每一个物品，可以选择放入（左子树）或者不放入（右子树）。<br>依次对每个节点进行搜索，得到最优解。</p>
<p>public class 零一背包 {<br>    &#x2F;*<br>     * 物品 A B C D E F G<br>     * 重量 35 30 60 50 40 10 25<br>     * 价值  10  40  30  50  35  40  30<br>     *<br>     * *&#x2F;<br>    &#x2F;&#x2F;物品数量<br>    int n&#x3D;7;<br>    &#x2F;&#x2F;背包容量<br>    int capacity&#x3D;150;<br>    &#x2F;&#x2F;物品重量数组<br>    double weight[]&#x3D; {35,30, 60, 50, 40, 10, 25};<br>    &#x2F;&#x2F;物品价值数组<br>    double value[]&#x3D; {10,  40,  30,  50,  35,  40,  30};</p>
<pre><code>//最大价值
int maxValue = 0;
//当前最大价值
int currentValue;
//当前重量
int currentWeight;
// 装入方法数组
int[] way = new int[n];
//最佳装入方法数组
int[] bestWay = new int[n];

/*
 * 回溯算法设计
 * */
public void backTrack(int t) &#123;
    // 已经搜索到根节点
    if (t &gt; n - 1) &#123;
        if (currentValue &gt; maxValue) &#123;
            maxValue = currentValue;
            for (int i = 0; i &lt; n; i++)
                bestWay[i] = way[i];
        &#125;
        return;
    &#125;
    // 搜索左边节点
    if (currentWeight + weight[t] &lt;= capacity) &#123;
        currentWeight += weight[t];
        currentValue += value[t];
        way[t] = 1;
        //回溯
        backTrack(t + 1);
        currentWeight -= weight[t];
        currentValue -= value[t];
        way[t] = 0;
    &#125;
    // 不装入这个物品，直接搜索右边的节点
    if (bound(t + 1) &gt;= maxValue) &#123;
        backTrack(t + 1);
    &#125;
&#125;

// 用于计算剩余物品的最高价值上界
public double bound(int k) &#123;
    double maxLeft = currentValue;
    int leftWeight = capacity - currentWeight;
    // 尽力依照单位重量价值次序装剩余的物品
    while (k &lt;= n - 1 &amp;&amp; leftWeight &gt; weight[k]) &#123;
        leftWeight -= weight[k];
        maxLeft += value[k];
        k++;
    &#125;
    // 不能装时，用下一个物品的单位重量价值折算到剩余空间。
    if (k &lt;= n - 1) &#123;
        maxLeft += value[k] / weight[k] * leftWeight;
    &#125;
    return maxLeft;
&#125;

public static void main(String[] args) &#123;
    零一背包 knspsack2 = new 零一背包();
    knspsack2.backTrack(0);
    System.out.println(&quot;该背包能够取到的最大价值为:&quot; + knspsack2.maxValue);
    System.out.println(&quot;当前背包的重量为:&quot; + knspsack2.capacity);
    System.out.println(&quot;物品的取出方法为取出的方法为:&quot;);
    for (int i : knspsack2.bestWay)
        System.out.print(i + &quot;  &quot;);
&#125;
</code></pre>
<p>}</p>
<h2 id="五、分支限界"><a href="#五、分支限界" class="headerlink" title="五、分支限界"></a>五、分支限界</h2><p>回溯算法是深度优先，而分支限界是广度优先的一个经典例子<br>回溯法一般遍历整个空间，获取问题的所有解，<br>而分支限界法则是获取一个解(一般来说要获取最优解)</p>
<p>分支限界是加快搜索速度的一种技术<br>代价函数:<br>    计算函数: 搜索书的结点<br>    值: 极大化问题是以该点为根的子树所有可行解的值的上界(极小化问题的下界)<br>    性质: 对极大化问题父节点代价不小于结点的代价(极小化问题相反)<br>停止分支回溯父结点的依据<br>    1. 不满足约束条件<br>    2. 对于极大化问题,代价函数值小于当前界(对于极小化问题是大于界)</p>
<p>界的更新:<br>    对极大化问题,如果一个新的可行解的优化函数值大于(极小化问题为小于)当前的界,则把界更新为该可行解的值</p>
<p>界: 当前得到的可行解的目标函数的最大值(极小化问题相反)<br>界初值: 极大化问题初值为0(极小化问题为最大值)</p>
<p>经典问题: 圆排列问题、最大团问题、连续邮资问题</p>
<p>#案例1. 圆排列问题<br>给定n个圆的半径序列，各圆与底线相切排列<br>假定每个圆占大于1的长度，求具有最小长度ln的圆的排列顺序</p>
<p>解： &lt;i1,i2,…,in&gt;为1，2，…，n的排列<br>部分解向量&lt;i1,i2,…,ik&gt;：表示前k个圆已经排好<br>令B&#x3D;{i1,i2,…,ik}<br>下一个圆选择ik+1</p>
<p>约束条件：ik+1 属于 {1,2,…,n}-B<br>界：当前得到的最小圆排列长度</p>
<p>代价函数：<br>     算法已选择好1～k个圆<br>     rk：第k个圆的半径<br>     dk：第k-1个圆到第k个圆的圆心水平距离<br>     xk：第k个圆的圆心坐标，规定x1&#x3D;0<br>     lk：第1～k个圆的排列长度<br>     Lk：放好1～k个圆以后，对应结点的代价函数值  Lk &lt;&#x3D; ln<br>xk &#x3D; xk-1 + dk<br>部分排列长度： lk &#x3D; xk+rk+r1<br>排列长度ln &#x3D; xk+ dk+1 + dk+2 + … + dn + rn + r1<br>dk &#x3D; 开方（（rk + rk-1）平方 - （rk - rk-1）平方）<br>   &#x3D; 2开方（rk-1 × rk）<br>ln &#x3D; xk + dk+1 + dk+2 +…+ rn + r1<br>Lk &#x3D; xk + （2n -2k + 1）r + r1<br>r &#x3D; min（rij，rk）</p>
<p>实例：<br>输入： R&#x3D;{1,1,2,2,3,5}<br>      排列 &lt;1，2，3，4，5，6&gt;</p>
<p>public class 圆排列问题 {</p>
<pre><code>public int n;//待排列圆的个数
public float min;//当前最优值
public float[] x;//当前圆排列圆心横坐标
public float[] r;//当前圆排列
public float circlePerm(int nn,float[] rr)&#123;
    n=nn;
    r=rr;
    min=1000000;
    x=new float[n+1];
    backtrack(1);
    return min;
&#125;
public void backtrack(int t)&#123;
    if(t&gt;n)
        compute();
    else&#123;
        for(int j=t;j&lt;=n;j++)&#123;
            swap(r,t,j);
            float centerx=center(t);
            if(centerx+r[t]+r[1]&lt;min)&#123;//下界约束
                x[t]=centerx;
                backtrack(t+1);
            &#125;
            swap(r,t,j);
        &#125;
    &#125;
&#125;
public void swap(float[] r,int i,int j)&#123;
    float temp=r[i];
    r[i]=r[j];
    r[j]=temp;
&#125;
public float center(int t)&#123;//计算当前所选择圆的圆心横坐标
    float temp=0;
    for(int j=1;j&lt;t;j++)&#123;
        float valuex=(float) (x[j]+2.0*Math.sqrt(r[t]*r[j]));
        if(valuex&gt;temp)
            temp=valuex;
    &#125;
    return temp;
&#125;
public void compute()&#123;//计算当前圆排列的长度
    float low=0;
    float high=0;
    for(int i=1;i&lt;=n;i++)&#123;
        if(x[i]-r[i]&lt;low) low=x[i]-r[i];
        if(x[i]+r[i]&gt;high) high=x[i]+r[i];
    &#125;
    if(high-low&lt;min)
        min=high-low;
&#125;
public static void main(String[] args) &#123;
    int n=3;
    float[] r=&#123;0,1,1,2&#125;;//r下标从1开始， 0无用，只是凑数
    圆排列问题 c=new 圆排列问题();
    float min=c.circlePerm(n, r);
    System.out.println(&quot;最小圆排列长度为&quot;+min);
&#125;
</code></pre>
<p>}</p>
<p>&#x2F;*<br>输出：<br>最小圆排列长度为7.656854<br>*&#x2F;</p>
<p>#案例2. 最大团问题</p>
<p>问题： 无向图G&#x3D;&lt;V,E&gt;，求G的最大团<br>G的子图： 点都属于V，边都属于E<br>补图： 原来没边的都有边，有边的没了边</p>
<p>团： G的完全子图， 即任意两个顶点之间都有边的子图<br>最大团： 顶点数最多的团<br>独立集： 任意两点都没边</p>
<p>解： &lt;x1,x2,…,xn&gt; 为0-1向量，xk&#x3D;1表示顶点k属于最大团<br>约束条件： 该顶点与当前团内每个顶点都有边相连<br>界： 当前已检索到的极大团的顶点数<br>代价函数： F &#x3D; Cn + n - K<br>Cn为目前团的顶点数， k为结点层数</p>
<p>public class 最大团问题 {</p>
<pre><code>public int[] x;//当前解（x[i]=1表示i点在最大团中，=0表示不在团中）
public int n;//图G的顶点数
public int cn;//当前顶点数
public int bestn;//当前最大顶点数
public int[] bestx;//当前最优解
public int[][] a;//图G的邻接矩阵,0：不连通；1：连通
public int count;//图G的最大团个数
public void backtrack(int i)&#123;
    if(i&gt;n)&#123;
        for(int j=1;j&lt;=n;j++)&#123;
            bestx[j]=x[j];
            System.out.print(x[j]+&quot; &quot;);
        &#125;
        System.out.println();
        bestn=cn;
        count++;
        return;
    &#125;
    else&#123;
        boolean ok=true;
        for(int j=1;j&lt;i;j++)&#123;//检查顶点i是否与当前团全部连接
            if(x[j]==1&amp;&amp;a[i][j]==0)&#123;
                ok=false;
                break;
            &#125;
        &#125;
        if(ok)&#123;//从顶点i到已选入的顶点集中每一个顶点都有边相连
            //进入左子树
            x[i]=1;
            cn++;
            backtrack(i+1);
            x[i]=0;
            cn--;
        &#125;
        if(cn+n-i&gt;=bestn)&#123;//当前顶点数加上未遍历的课选择顶点&gt;=当前最优顶点数目时才进入右子树;如果不需要找到所有的解，则不需要等于
            //进入右子树
            x[i]=0;
            backtrack(i+1);
        &#125;
    &#125;
&#125;
public int maxclique(int nn,int[][] aa)&#123;
    //初始化
    n=nn;
    a=aa;
    x=new int[n+1];
    bestx=x;
    cn=0;
    bestn=0;
    count=0;
    backtrack(1);
    return bestn;
&#125;
public static void main(String[] args) &#123;
    int[][] a=&#123;&#123;-1,-1,-1,-1,-1,-1&#125;,&#123;-1,0,1,0,1,1&#125;,&#123;-1,1,0,1,0,1&#125;,&#123;-1,0,1,0,0,1&#125;,&#123;-1,1,0,0,0,1&#125;,&#123;-1,1,1,1,1,0&#125;&#125;;//a的下标从1开始，-1的值无用
    int n=5;
    最大团问题 m=new 最大团问题();
    System.out.println(&quot;图G的最大团解向量为：&quot;);
    System.out.println(&quot;图G的最大团顶点数为：&quot;+m.maxclique(n, a));
    System.out.println(&quot;图G的最大团个为：&quot;+m.count);
&#125;
</code></pre>
<p>}</p>
<p>&#x2F;*<br>输出：<br>图G的最大团解向量为：<br>1 1 0 0 1<br>1 0 0 1 1<br>0 1 1 0 1<br>图G的最大团顶点数为：3<br>图G的最大团个为：3<br>*&#x2F;</p>
<p>#案例3. 连续邮资问题</p>
<p>连续邮资问题：<br>给定n种不同面值的邮票，每个信封至多贴m张<br>试给出邮票的最佳设计，使得从1开始<br>增量为1的连续邮资区间达到最大</p>
<p>实例： n&#x3D;5， m&#x3D;4<br>设计1： 面值 X &#x3D; &lt;1，3，11，15，32&gt;<br>        邮资连续区间 {1,2,…,70}<br>设计2： 面值 X &#x3D; &lt;1，6，10，20，30&gt;<br>        邮资连续区间{1,2,3,4}</p>
<p>约束条件：在结点x1…xi处，邮资最大连续区间为{1，…,ri}<br>xi+1 的取值范围是<br>{xi+1,…,ri+1}<br>若xi+1&gt;ri+1，ri+1的邮资无法支付<br>yi（j）： 用至多m张面值 xi的邮票加上x1，x2，…，xi-1面值的邮票贴j邮资时的最少邮票数<br>则：<br>yi（j） &#x3D; min{t + yi-1(j - txi) }<br>y1(j) &#x3D; j<br>ri &#x3D; min{j|yi(j) &lt;&#x3D; m, yi(j+1) &gt; m}</p>
<p>界： max， m张邮票连续付的最大邮资</p>
<p>public class 连续邮资问题 {<br>    int m;<br>    int n;<br>    int stamps[];<br>    int maxNum &#x3D; 0;<br>    int[] tempset;<br>    int current;<br>    int rightPos;<br>    int base;<br>    public 连续邮资问题(int m,int n,int[] stamps){<br>        this.m &#x3D; m;<br>        this.n &#x3D; n;<br>        this.stamps &#x3D; stamps;<br>        check();<br>        printResult();<br>    }</p>
<pre><code>public void check()&#123;
    tempset = new int[stamps[(stamps.length-1)]*4+1];
    maxNum = m;//因为第一个确定是1，所以初始化最大的面值就是 1*m
    for (int i=1;i&lt;5;i++)&#123;
        int min = Math.max(stamps[i],maxNum)+1;;
        int max = stamps[i]*m;
        if (min &lt; stamps[i]+1)&#123;
            return;
        &#125;
        maxNum = min-1;
        tempset[maxNum]=1;
        if (!checkSpan(min,max,i))&#123;
            return;
        &#125;
    &#125;
&#125;

public boolean checkSpan(int min,int max,int rightPos)&#123;
    base = min;
    current=stamps[rightPos];
    this.rightPos = rightPos;
    backtrace(0);
    if (tempset[min] == 0)&#123;
        return false;
    &#125;
    for (int i=min;i&lt;max;i++)&#123;
        if (tempset[i] == 0)&#123;
            return true;
        &#125;
        else&#123;
            maxNum++;
        &#125;
    &#125;
    return true;
&#125;

public void backtrace(int i)&#123;
    if (i &gt;= (m-1))&#123;
        return;
    &#125;
    else&#123;
        for (int j=0;j&lt;rightPos+1;j++)&#123;
            current += stamps[j];
            if (current &gt;= base)&#123;
                tempset[current] = 1;
            &#125;
            backtrace(i+1);
            current -= stamps[j];
        &#125;
    &#125;
&#125;

public void printResult()&#123;
    System.out.println(maxNum);
&#125;

public static void main(String args[])&#123;
    int m=4;
    int n=5;
    int[] stamps=&#123;1,3,11,15,32&#125;;
    new 连续邮资问题(m,n,stamps);
&#125;
</code></pre>
<p>}</p>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/shiqing/about" rel="external nofollow noreferrer">世庆</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://shiqing.gitee.io/shiqing/2021/04/27/suan-fa/algorithm/">https://shiqing.gitee.io/shiqing/2021/04/27/suan-fa/algorithm/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="/shiqing/about" target="_blank">世庆</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/shiqing/tags/%E7%AE%97%E6%B3%95/">
                                    <span class="chip bg-color">算法</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/shiqing/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/shiqing/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/shiqing/medias/reward/alipay.jpg" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/shiqing/medias/reward/wechat.png" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/shiqing/2021/04/29/cao-zuo-xi-tong/cao-zuo-xi-tong-di-yi-zhang/">
                    <div class="card-image">
                        
                        
                        <img src="/shiqing/medias/featureimages/15.jpg" class="responsive-img" alt="操作系统第一章">
                        
                        <span class="card-title">操作系统第一章</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2021-04-29
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/shiqing/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" class="post-category">
                                    操作系统
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/shiqing/tags/%E6%A6%82%E8%BF%B0/">
                        <span class="chip bg-color">概述</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/shiqing/2021/04/26/suan-fa/sortsollutions/">
                    <div class="card-image">
                        
                        
                        <img src="/shiqing/medias/featureimages/9.jpg" class="responsive-img" alt="SortSollutions.md">
                        
                        <span class="card-title">SortSollutions.md</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2021-04-26
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/shiqing/categories/%E7%AE%97%E6%B3%95/" class="post-category">
                                    算法
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/shiqing/tags/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/">
                        <span class="chip bg-color">排序算法</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>



<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/shiqing/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/shiqing/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/shiqing/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/shiqing/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/shiqing/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('0'),
            headingSelector: 'h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




        <footer class="page-footer bg-color">
    
    <div class="container row center-align" style="margin-bottom: 0px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2019-2024</span>
            
            <span id="year">2019</span>
            <a href="/shiqing/about" target="_blank">ShiQing</a>
            |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a>
            |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a>
            <br>
            
            
            
            
            
            
            <span id="busuanzi_container_site_pv">
                |&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;<span id="busuanzi_value_site_pv"
                    class="white-color"></span>&nbsp;次
            </span>
            
            
            <span id="busuanzi_container_site_uv">
                |&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;<span id="busuanzi_value_site_uv"
                    class="white-color"></span>&nbsp;人
            </span>
            
            <br>
            
            <br>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/blinkfox" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2528393970@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>



    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2528393970" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2528393970" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







    <a href="/shiqing/atom.xml" class="tooltipped" target="_blank" data-tooltip="RSS 订阅" data-position="top" data-delay="50">
        <i class="fas fa-rss"></i>
    </a>

</div>
    </div>
</footer>

<div class="progress-bar"></div>


        <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/shiqing/search.xml', 'searchInput', 'searchResult');
});
</script>

        <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


        <script src="/shiqing/libs/materialize/materialize.min.js"></script>
        <script src="/shiqing/libs/masonry/masonry.pkgd.min.js"></script>
        <script src="/shiqing/libs/aos/aos.js"></script>
        <script src="/shiqing/libs/scrollprogress/scrollProgress.min.js"></script>
        <script src="/shiqing/libs/lightGallery/js/lightgallery-all.min.js"></script>
        <script src="/shiqing/js/matery.js"></script>

        <!-- Baidu Analytics -->

        <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

        
        <script src="/shiqing/libs/others/clicklove.js" async="async"></script>
        
        
        <script async src="/shiqing/libs/others/busuanzi.pure.mini.js"></script>
        

        <script type="text/javascript">
            var OriginTitile = document.title,
                st;
            document.addEventListener("visibilitychange", function () {
                document.hidden ? (document.title = "看不见我~看不见我~", clearTimeout(st)) : (document.title =
                    "(๑•̀ㅂ•́) ✧被发现了～", st = setTimeout(function () {
                        document.title = OriginTitile
                    }, 3e3))
            })
        </script>

        <!-- 背景樱花飘落特效 -->
        
            <script type="text/javascript">
                //只在桌面版网页启用特效
                var windowWidth = $(window).width();
                if (windowWidth > 768) {
                    document.write('<script type="text/javascript" src="/js/xuehuapiaoluo.js"><\/script>');
                }
            </script>
        

        

        


        
        

        

        

        
        <script src="/shiqing/libs/instantpage/instantpage.js" type="module"></script>
        

    </body>

</html>
